package com.base;

public class 并查集 {
    //2368
    class UnionFind {
        private int[] f;//父亲
        private int[] rank;//深度

        public UnionFind(int n) {
            f = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                f[i] = i;
            }
        }

        public void merge(int x, int y) {
            int rx = find(x);
            int ry = find(y);
            if (rx != ry) {
                if (rank[rx] > rank[ry]) {
                    f[ry] = rx;
                } else if (rank[rx] < rank[ry]) {
                    f[rx] = ry;
                } else {
                    f[ry] = rx;
                    rank[rx]++;
                }
            }
        }

        public int find(int x) {
            if (x != f[x]) {
                x = find(f[x]);
            }
            return f[x];
        }
        //有多少与x同父的
        public int count(int x) {
            int cnt = 0;
            int rt = find(x);
            for (int i = 0; i < f.length; i++) {
                if (rt == find(i)) {
                    cnt++;
                }
            }
            return cnt;
        }
        //有多少组：从前到后看看有多少 直接父 为自己的
    }
}
